package sort;

import java.util.Arrays;

public class MergeSort {
    private static final int[] a = {2, 4, 1, 5, 7, 3, 9, 6, 8, 0};

    public static void main(String[] args) {
        mergeSort(0, 9);
        System.out.println(Arrays.toString(a));
    }

    private static void mergeSort(int p, int r) {
        if (p < r) {
            int q = Math.floorDiv(r + p, 2);
            mergeSort(p, q);
            mergeSort(q + 1, r);
            merge(p, q, r);
        }
    }

    //    需要合并的两个子数组是连续的，参数为，开始，中间，结束的下表值
    private static void merge(int p, int q, int r) {
        int[] left = new int[q - p + 2];
        int[] right = new int[r - q + 1];
//        设置哨兵，方便循环比较
        left[q - p + 1] = Integer.MAX_VALUE;
        right[r - q] = Integer.MAX_VALUE;
        System.arraycopy(a, p, left, 0, q - p + 1);
        System.arraycopy(a, q + 1, right, 0, r - q);
        int leftIndex = 0;
        int rightIndex = 0;
        for (int k = p; k <= r; k++) {
            if (left[leftIndex] < right[rightIndex]) {
                a[k] = left[leftIndex];
                leftIndex++;
            } else {
                a[k] = right[rightIndex];
                rightIndex++;
            }
        }
    }
}
